////////////////////////////////////////////////////////////////////////////////////
//
//      FILE:       list.h: simple realization of linked list
//      PROJECT:
//      CREATED:    25-Dec-2001 initial implemetation
//      AUTHOR:     Vladimir Gumenuk
//
//      Revision:   27-May-2002
//      Revision:   21-Aug-2002
//      Revision:   18-Sep-2002 now this list can store the pointers to objects only!!!
//      Revision:   07-Dec-2002 EraseItem - bug fixed
//      Revision:   22-Aug-2003 old stack renamed to CPtrStack - for pointers only!, new list added.
//      Revision:   19-Jan-2004 list: T *m_pItem -> T m_Item
//      Revision:   22-May-2004 list: add Iterator functionality
//      Revision:   02-Apr-2005 list: items inited via copy constructor instead of assign operator
//                              class CVector added
//      Revision:   25-Feb-2006 list::remove_item - fixed bug: m_pEnd is now correctly updated
//      Revision:   09-Mar-2008 old CPtrStack removed. 
//      Revision:   22-Mar-2008 file included into Xort project.
//  
//
//     Copyright(c) 2014, Vladimir Gumenuk
//     All rights reserved.
//
//     Redistribution and use in source and binary forms, with or without modification, 
//     are permitted provided that the following conditions are met :
//
//     1. Redistributions of source code must retain the above copyright notice, 
//        this list of conditions and the following disclaimer.
//     2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and 
//        the following disclaimer in the documentation and / or other materials provided with the distribution.
//     3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse 
//        or promote products derived from this software without specific prior written permission.
//
//     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND 
//     ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 
//     OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL 
//     THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 
//     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 
//     OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
//     HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 
//     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, 
//     EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
////////////////////////////////////////////////////////////////////////////////////

#pragma once

template<class T>
class CCopySimpleType
{
public:
    static inline void Copy( T& dst, const T& src ) { dst = src; }
};

template<class T>
class CCopyObject
{
public:
    static inline void Copy( T& dst, const T& src ) {
        if( dst )
            dst->Release();
        dst = src;
        if( dst )
            dst->AddRef();
    }
};

template<class T>
class CDeleteSimpleType
{
public:
    static inline void Delete( T& t ) { t = 0; }
};

template<class T>
class CDeleteObject
{
public:
    static inline void Delete( T& t ) { 
        if( t ) {
            t->Release();
            t = 0;
        }
    }
};


template <class T, class CopyItem, class DeleteItem>
class xlist : public xobject
{
    template <class U>
    class CContainer
    {
        friend class xlist<T, CopyItem, DeleteItem>;
        friend class CListIterator;
    protected: U    m_Item;
    private:
        CContainer *m_pPrev, *m_pNext;
        
        // for push back
        CContainer( CContainer<U> *pPrev, const T& Item ) {
            m_Item = 0;
            CopyItem::Copy( m_Item, Item );
            m_pPrev = pPrev; m_pNext = 0;
            if( pPrev ) pPrev->m_pNext = this;
        }
        
        // for push front
        CContainer( const T& Item, CContainer<U> *pNext ) {
            m_Item = 0;
            CopyItem::Copy( m_Item, Item );
            m_pPrev = 0; m_pNext = pNext;
            if( pNext ) pNext->m_pPrev = this;
        }

        ~CContainer() { DeleteItem::Delete( m_Item ); }

        void inverse_to_begin( CContainer<U> *pPrev ) {
            if( m_pPrev ) m_pPrev->inverse_to_begin( this );
            m_pNext = m_pPrev; m_pPrev = pPrev;
        }
    };
    
public:
    class CListIterator
    {
    friend class xlist<T, CopyItem, DeleteItem>;
        CContainer<T>    *m_pNext;
        inline CContainer<T> * get_container() const { return m_pNext; }
    public:
        CListIterator() { m_pNext = 0; }
        CListIterator( CContainer<T> *p ) { m_pNext = p; }
        CListIterator( const CListIterator& i ) { m_pNext = i.m_pNext; }
        inline void operator++(int) { if( m_pNext ) m_pNext = m_pNext->m_pNext; }
        inline void operator--(int) { if( m_pNext ) m_pNext = m_pNext->m_pPrev; }
        inline CListIterator& operator= ( const CContainer<T> *pC ) { m_pNext = pC; return (*this); }
        inline int operator== ( const CContainer<T> *pC ) { return ( m_pNext == pC ) ? 1 : 0; }
        inline int operator!= ( const CContainer<T> *pC ) { return ( m_pNext != pC ) ? 1 : 0; }
        inline operator T* () { return ( m_pNext ) ? &m_pNext->m_Item : 0; }
        inline operator T& () { return m_pNext->m_Item; }
        inline void operator+= ( dword i ) { if( i ) { do { operator++( i );} while( --i ); } }
        inline T item() { return ( m_pNext ) ? m_pNext->m_Item : 0; }
        inline int isContainerValid() const { return ( m_pNext ) ? 1 : 0; }
    };

    typedef CListIterator    iterator;

    // xobject implementation
    virtual int Init( symbolref pSymbol, XortNativeInterface *pExternalObj ) { return XORT_OK; }
    virtual dword GetType() { return t_list; };
    virtual int Invoke( dword dwFuncIndex, XRuntime *pRuntime ) { 
        return ERR_METHOD_NOT_IMPL; 
    }
    virtual int Put( dword dwVarIndex, const XortElement& Value ) { 
        return ERR_METHOD_NOT_IMPL; 
    }
    virtual int Get( dword dwVarIndex, XortElement& Value ) { 
        return ERR_METHOD_NOT_IMPL; 
    }
    virtual dword GetVariablesCount() { return 0; }

    dword GetTemplateType() { return m_dwTemplateType; }

protected:
    CContainer<T>    *m_pBegin, *m_pEnd, *m_pWork, *m_pHelper;
    dword      m_iItemsCount;
    dword      m_dwTemplateType;

    CContainer<T> * get_ItemContainer( dword iIndex ) {
        if( m_iItemsCount <= iIndex ) return 0;
        CContainer<T> *pTemp = m_pBegin;
        dword i = 0;
        while( i != iIndex ) { pTemp = pTemp->m_pNext; i++; }
        return pTemp;
    }
    
    CContainer<T> * get_ItemContainer( const T *pDel ) {
        if( m_iItemsCount == 0 ) return 0;
        CContainer<T> *pTemp = m_pBegin;
        while( pTemp ) {
            if( &pTemp->m_Item == pDel ) return pTemp;
            pTemp = pTemp->m_pNext;
        }
        return 0;
    }

    iterator remove_item( CContainer<T> *pItem ) { // returns next iterator
        CContainer<T> *pRet = 0;
        if( pItem ) {
            CContainer<T> *pPrev = pItem->m_pPrev;
            CContainer<T> *pNext = pItem->m_pNext;
            delete pItem;
            if( pPrev ) {// update links
                pPrev->m_pNext = pNext; 
                if( pNext ) {
                    pNext->m_pPrev = pPrev;
                    pRet = pNext;
                } else { // we deleted the bottom of the xlist
                    m_pEnd = pPrev;
                    pRet = pPrev;
                }
            } else { // we deleted the top of the xlist
                m_pBegin = pNext;
                pRet = pNext;
                if( m_pBegin ) m_pBegin->m_pPrev = 0;
            }
            if( --m_iItemsCount == 0 ) m_pBegin = m_pEnd = 0;
        }
        return CListIterator( pRet );
    }

public:
    xlist() { m_pBegin = 0; m_pEnd = 0; m_pWork = 0; m_iItemsCount = 0; m_dwTemplateType = 0; }
    xlist( const xlist<T, CopyItem, DeleteItem>& copy ) {
        m_pBegin = 0; m_pEnd = 0; m_pWork = 0; m_iItemsCount = 0; m_dwTemplateType = 0;
        iterator theIter = copy.begin();
        T * pData = NULL;
        while( (pData = (T*)theIter) ) {
            push_back( *pData );
            theIter++;
        }
    }
    virtual ~xlist() { clear(); }
    
    void clear() {
        CContainer<T> *pCont = m_pBegin;
        while( pCont ) {
            CContainer<T> *pDel = pCont;
            pCont = pCont->m_pNext;
            delete pDel;
        }
        m_pWork = m_pHelper = m_pBegin = m_pEnd = 0;
        m_iItemsCount = 0;
    }

    inline dword push_front( const T& Item ) {
        if( m_pBegin ) {
            CContainer<T> *pTemp = new CContainer<T>( Item, m_pBegin );
            m_pBegin = pTemp;
        } else {
            m_pBegin = new CContainer<T>( Item, 0 );
            m_pWork = m_pEnd = m_pBegin;
        }
        if( m_pBegin ) {
            m_iItemsCount++;
            return m_iItemsCount;
        }
        return 0;
    }

    inline dword push_back( const T& Item ) {
        if( m_pEnd ) {
            CContainer<T> *pTemp = new CContainer<T>( m_pEnd, Item );
            m_pEnd = pTemp;
        } else {
            m_pEnd = new CContainer<T>( 0, Item );
            m_pWork = m_pBegin = m_pEnd;
        }
        if( m_pEnd ) {
            m_iItemsCount++;
            return m_iItemsCount;
        }
        return 0;
    }

    inline dword pop_front() {
        if( m_pBegin ) {
            CContainer<T> *pTemp = m_pBegin->m_pNext;
            delete m_pBegin;
            m_pBegin = pTemp;
            if( m_pBegin ) m_pBegin->m_pPrev = 0;
            if( --m_iItemsCount == 0 ) m_pEnd = m_pBegin = 0;
            return m_iItemsCount;
        }
        return 0;
    }
    
    inline dword pop_back() {
        if( m_pEnd ) {
            CContainer<T> *pTemp = m_pEnd->m_pPrev;
            delete m_pEnd;
            m_pEnd = pTemp;
            if( m_pEnd ) m_pEnd->m_pNext = 0;
            if( --m_iItemsCount == 0 ) m_pBegin = m_pEnd = 0;
            return m_iItemsCount;
        }
        return 0;
    }

    inline const T& top() { return m_pBegin->m_Item; }
    
    inline bool empty() { return ( ( m_iItemsCount ) ? false : true); }
    
    inline const T& get_item( dword iIndex ) const {
        CContainer<T> *pTemp = m_pBegin;
        dword i = 0;
        while( i != iIndex ) { pTemp = pTemp->m_pNext; i++; }
        return pTemp->m_Item;
    }

    inline dword size() const { return m_iItemsCount; }
    
    inline void reset_to_begin() { m_pWork = m_pBegin; }
    
    inline T* next() {
        m_pHelper = m_pWork;
        if( m_pWork ) m_pWork = m_pWork->m_pNext;
        return ( m_pHelper ) ? &m_pHelper->m_Item : 0;
    }
    
    inline void reset_to_end() { m_pWork = m_pEnd; }
    
    inline T* prev() {
        m_pHelper = m_pWork;
        if( m_pWork ) m_pWork = m_pWork->m_pPrev;
        return ( m_pHelper ) ? &m_pHelper->m_Item : 0;
    }

    inline const T& operator[] ( dword iIndex ) const { return get_item( iIndex ); }
    
    void inverse() {
        if( m_pEnd ) { m_pEnd->inverse_to_begin( 0 );
            CContainer<T> *pTemp = m_pBegin;
            m_pBegin = m_pEnd;
            m_pEnd = pTemp;
        }
    }
    
    void erase( dword iIndex ) {
        CContainer<T> *pTemp = get_ItemContainer( iIndex );
        remove_item( pTemp );
    }

    void erase( const T *pDel ) {
        CContainer<T> *pTemp = get_ItemContainer( pDel );
        remove_item( pTemp );
    }

    iterator erase( const iterator& iter ) {
        CContainer<T> *pTemp = iter.get_container();
        return remove_item( pTemp );
    }

    void insert_after( const iterator& Iter, const T& Item ) {
        if( !Iter.m_pNext ) {
            push_back( Item );
        } else {
            CContainer<T> *pNext = Iter.m_pNext->m_pNext;
            if( !pNext ) {
                push_back( Item );
            } else {
                CContainer<T> *pItem = new CContainer<T>( Iter.m_pNext, Item );
                pNext->m_pPrev = pItem;
                pItem->m_pNext = pNext; 
                m_iItemsCount++;
            }
        }
    }

    void insert_before( const iterator& Iter, const T& Item ) {
        if( !Iter.m_pNext ) {
            push_front( Item );
        } else {
            CContainer<T> *pPrev = Iter.m_pNext->m_pPrev;
            if( !pPrev ) {
                push_front( Item );
            } else {
                CContainer<T> *pItem = new CContainer<T>( Item, Iter.m_pNext );
                pPrev->m_pNext = pItem;
                pItem->m_pPrev = pPrev; 
                m_iItemsCount++;
            }
        }
    }

    void operator= ( const xlist< T, CopyItem, DeleteItem> &lst ) {
        clear();
        xlist<T, CopyItem, DeleteItem> *p = const_cast< xlist<T, CopyItem, DeleteItem> * >( &lst );
        if( p->size() ) { p->reset_to_begin();
            const T* pItem;
            while( (pItem = p->next()) ) { push_back( *pItem ); }
        }
    }

    dword copy( xlist< T, CopyItem, DeleteItem> &lst ) {
        lst.clear();
        if( size() ) {
            reset_to_begin();
            const T* pItem;
            while( ( pItem = next() ) ) { lst.push_back( *pItem ); }
        }
        return lst.size();
    }

    inline iterator begin() const { return CListIterator( m_pBegin ); }
    inline iterator end() const { return CListIterator( m_pEnd ); }

};


//////////////////////////////////////////////////////////////////////////
// Class xarray - simple array of simple types
template<class T, class CopyItem, class DeleteItem>
class xarray : public xobject
{
protected:
    T     *m_pItems;
    dword  m_dwCount;
    dword  m_dwAllocated;
    dword  m_dwTemplateType;

public:
    xarray() { m_pItems = 0; m_dwCount = m_dwAllocated = 0; m_dwTemplateType = 0; }
    virtual ~xarray() { clear(); }

    dword GetTemplateType() { return m_dwTemplateType; }

    virtual int Init( symbolref pSymbol, XortNativeInterface *pExternalObj ) { return XORT_OK; }
    virtual int Invoke( dword dwFuncIndex, XRuntime *pRuntime ) { 
        return ERR_METHOD_NOT_IMPL;
    }
    virtual int Put( dword dwVarIndex, const XortElement& Value ) { 
        return ERR_METHOD_NOT_IMPL; 
    }
    virtual int Get( dword dwVarIndex, XortElement& Value ) { 
        return ERR_METHOD_NOT_IMPL;
    }
    virtual dword GetVariablesCount() { return 0; }

    dword reserve( dword iNumItems ) {
        if( m_dwAllocated < iNumItems ) {
            T *p = new T[iNumItems];
            if( !p )
                return 0;
            for( dword i = 0; i < iNumItems; i++ )
                p[i] = 0;
            if( m_pItems ) {
                for( dword i = 0; i < m_dwCount; i++ ) {
                    CopyItem::Copy( p[i], m_pItems[i] );
                    DeleteItem::Delete( m_pItems[i] );
                }
                delete []m_pItems;
            }
            m_dwAllocated = iNumItems;
            m_pItems = p;
        }
        return m_dwAllocated;
    }

    dword add( const T& Item ) { // add now return the index of the element
        if( m_dwCount == m_dwAllocated ) {
            dword iNewSize = (m_dwAllocated == 0) ? 2 : ( m_dwCount * 2 );
            if( !reserve( iNewSize ) )
                return 0;
        }
        CopyItem::Copy( m_pItems[m_dwCount], Item );
        m_dwCount++;
        return m_dwCount - 1; // index is zero-based :)
    }

    dword del() {
        if( m_dwCount > 0 ) {
            m_dwCount--;
            DeleteItem::Delete( m_pItems[m_dwCount] );
        }
        return m_dwCount;
    }

    void clear() {
        if( m_pItems ) {
            for( dword i = 0; i < m_dwCount; i++ ) {
                DeleteItem::Delete( m_pItems[i] );
            }
            delete []m_pItems;
            m_pItems = 0; m_dwCount = m_dwAllocated = 0;
        }
    }

    void deleteAt( dword idx ) {
        if( m_pItems && isValidIndex( idx ) ) {
            DeleteItem::Delete( m_pItems[idx] );
            m_pItems[idx] = 0;
        }
    }

    inline void zero() {
        if( m_pItems ) {
            for( dword i = 0; i < m_dwAllocated; i++ )
                DeleteItem::Delete( m_pItems[i] );
        }
    }

    inline bool canPut( dword idx ) const {
        return idx < m_dwCount ? true : false;
    }

    inline dword put( dword idx, const T& Item ) {
        if( idx < m_dwAllocated ) {
            CopyItem::Copy( m_pItems[idx], Item ); 
            return idx;
        }
        return 0;
    }

    inline bool canGet( dword idx ) const {
        return idx < m_dwCount ? true : false;
    }
    
    inline T& get( dword idx ) const {
        //if( idx < m_dwCount ) {
            return m_pItems[idx]; 
        //} // "no return" - this warning is very nice here!
    }

    inline bool empty() const { return ( m_dwCount > 0 ? false : true ); }

    inline dword count() const { return m_dwCount; }

    inline dword allocated() const { return m_dwAllocated; }

    inline T& operator[]( dword idx ) const { return m_pItems[idx]; }

    inline void* ptr( dword idx ) const { return &m_pItems[idx]; }

    // cheating function!
    inline dword set_itemsCount( dword dwCount ) {
        if( m_dwAllocated >= dwCount ) {
            m_dwCount = dwCount;
            return dwCount;
        }
        return 0;
    }

    dword copy( xarray<T, CopyItem, DeleteItem>& ar ) {
        ar.clear();
        for( dword i = 0; i < m_dwCount; i++ ) {
            ar.add( get( i ) );
        }
        return ar.count();
    }

    inline bool isValidIndex( dword idx ) const { return idx >= m_dwCount ? false : true; }

};

class xstack : public xarray<XortElement, CCopySimpleType<XortElement>, CDeleteSimpleType<XortElement> >
{
public:
    // for simplified stack implementation
    inline XortElement& top() {
        return m_pItems[ m_dwCount-1 ];
    }

    inline bool canPop() const {
        return m_dwCount > 0 ? true : false;
    }
    
    inline XortElement pop() {
        m_dwCount -= 1;
        XortElement x = m_pItems[ m_dwCount ];
        m_pItems[ m_dwCount ].Clear();
        return x;
    }

    // returns the index of the element
    inline dword push( const XortElement& Item ) {
        return add( Item );
    }
};

class ByteArray : public xarray<byte, CCopySimpleType<byte>, CDeleteSimpleType<byte> >
{
    struct TTConv {
        union {
            dword _u4;
            float _r4;
            qword _u8;
            real  _r8;
        };
    };

public:
    virtual ~ByteArray() { clear(); }

    dword storeByte( byte b )
    {
        return add( b );
    }
    
    byte getByte( dword dwAtIndex ) const
    {
        return get( dwAtIndex ); 
    }

    dword storeShort( short s )
    {
        add( x_lobyte( s ) );
        return add( x_hibyte( s ) );
    }

    short getShort( dword dwAtIndex ) const
    {
        byte b1 = get( dwAtIndex );
        byte b2 = get( dwAtIndex + 1 );
        short s = x_makeShort( b1, b2 );
        return s;
    }
    
    dword storeWord( word w )
    {
        add( x_lobyte( w ) );
        return add( x_hibyte( w ) );
    }
    word getWord( dword dwAtIndex ) const
    {
        byte b1 = get( dwAtIndex );
        byte b2 = get( dwAtIndex + 1 );
        word w = x_makeWord( b1, b2 );
        return w;
    }
    
    dword storeInt( int i )
    {
        word w1 = x_loword( i );
        word w2 = x_hiword( i );
        add( x_lobyte( w1 ) );
        add( x_hibyte( w1 ) );
        add( x_lobyte( w2 ) );
        return add( x_hibyte( w2 ) );
    }

    int getInt( dword dwAtIndex ) const
    {
        byte b1 = get( dwAtIndex );
        byte b2 = get( dwAtIndex + 1 );
        byte b3 = get( dwAtIndex + 2 );
        byte b4 = get( dwAtIndex + 3 );
        short s1 = x_makeShort( b1, b2 );
        short s2 = x_makeShort( b3, b4 );
        int i = x_makeInt( s1, s2 );
        return i;
    }
    
    dword storeDword( dword d )
    {
        word w1 = x_loword( d );
        word w2 = x_hiword( d );
        add( x_lobyte( w1 ) );
        add( x_hibyte( w1 ) );
        add( x_lobyte( w2 ) );
        return add( x_hibyte( w2 ) );
    }
    dword getDword( dword dwAtIndex ) const
    {
        byte b1 = get( dwAtIndex );
        byte b2 = get( dwAtIndex + 1 );
        byte b3 = get( dwAtIndex + 2 );
        byte b4 = get( dwAtIndex + 3 );
        short s1 = x_makeShort( b1, b2 );
        short s2 = x_makeShort( b3, b4 );
        dword dw = x_makeInt( s1, s2 );
        return dw;
    }
    
    dword storeLong( qlong l )
    {
        return storeQword( l );
    }
    qlong getLong( dword dwAtIndex ) const
    {
        int i1 = getInt( dwAtIndex );
        int i2 = getInt( dwAtIndex + 4 );
        qlong ql = x_makeLong( i1, i2 );
        return ql;
    }

    dword storeQword( qword q )
    {
        dword d1 = (dword)q;
        dword d2 = (dword)( q >> 32 );
        storeDword( d1 );
        return storeDword( d2 );
    }
    qword getQword( dword dwAtIndex ) const
    {
        dword d1 = getDword( dwAtIndex );
        dword d2 = getDword( dwAtIndex + 4 );
        qword qw = x_makeQword( d1, d2 );
        return qw;
    }

    dword storeFloat( float f )
    {
        TTConv x;
        x._r4 = f;
        return storeDword( x._u4 );
    }
    float getFloat( dword dwAtIndex ) const
    {
        TTConv x;
        x._u4 = getDword( dwAtIndex );
        return x._r4;
    }

    dword storeDouble( double r )
    {
        TTConv x;
        x._r8 = r;
        return storeQword( x._u8 );
    }

    double getDouble( dword dwAtIndex ) const
    {
        TTConv x;
        x._u8 = getQword( dwAtIndex );
        return x._r8;
    }

    dword storePointer( xobjectref p )
    {
#ifdef ARCH_64BIT
        return storeQword( (qword)p );
#else
        return storeDword( (dword)p );
#endif
    }

    xobjectref getPointer( dword dwAtIndex ) const
    {
#ifdef ARCH_64BIT
        return (xobjectref)getQword( dwAtIndex );
#else
        return (xobjectref)getDword( dwAtIndex );
#endif
    }
};

// ------------------------------------------------------------------------------------------



